package com.leetcode.No1793;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

public class Solution {
    public int maximumScore(int[] nums, int k) {
        Map<Integer, Integer> leftMax = new HashMap<>();
        Map<Integer, Integer> rightMax = new HashMap<>();

        TreeSet<Integer> maxSet = new TreeSet<>(Integer::compareTo);

        int max = nums[k];
        for (int i = k; i >= 0; --i) {
            max = Math.min(max, nums[i]);
            Integer tmpLeftMax = leftMax.get(max) == null ? 0 : leftMax.get(max);
            tmpLeftMax = Math.max(tmpLeftMax, max * (k - i + 1));
            leftMax.put(max, tmpLeftMax);
            maxSet.add(max);
        }

        max = nums[k];
        for (int i = k; i < nums.length; ++i) {
            max = Math.min(max, nums[i]);
            Integer tmpRightMax = rightMax.get(max) == null ? 0 : rightMax.get(max);
            tmpRightMax = Math.max(tmpRightMax, max * (i - k + 1));
            rightMax.put(max, tmpRightMax);
            maxSet.add(max);
        }

        int result = 0;
        for (Integer m : maxSet) {
            int left = (leftMax.get(m) == null) ? 0 : leftMax.get(m);
            int right = (rightMax.get(m) == null) ? 0 : rightMax.get(m);
            result = Math.max(result, left + right - m);
        }
        return result;
    }

    @Test
    public void test() {
        int[] nums = new int[]{1,4,3,7,4,5};
        int k = 3;
        System.out.println(maximumScore(nums, k));
    }
}
